import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Solution1 s = new Solution1();
        System.out.println(s.divide(10, 3));
        System.out.println(s.divide(7, -3));
        System.out.println(s.divide(2147483647, -1));
    }
}


//官方题解，二分查找
class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == Integer.MIN_VALUE){
            if(divisor == -1){
                return Integer.MAX_VALUE;
            }
            if(divisor == 1){
                return Integer.MIN_VALUE;
            }
        }
        if(divisor == Integer.MIN_VALUE){
            if(dividend == Integer.MIN_VALUE){
                return 1;
            }
            return 0;
        }

        boolean negative = false;
        if(dividend > 0){
            dividend = -dividend;
            negative = !negative;
        }
        if(divisor > 0){
            divisor = -divisor;
            negative = !negative;
        }

        int l = 0;
        int r = Integer.MAX_VALUE;
        //找到 divisor * z >= dividend 的最大z
        while(l <= r){
            //mid = (l + r) / 2, 注意溢出
            int mid = l + ((r - l) >> 1);
            if(quickAdd(divisor, mid, dividend)){
                if(mid == Integer.MAX_VALUE){
                    break;
                }
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }

        return negative ? -r : r;
    }

    /**
     * 快速加实现乘法
     * @param y 负数
     * @param z 正数
     * @param x 负数
     * @return y * z >= x是否成立
     */
    boolean quickAdd(int y, int z, int x){
        int ans = 0;
        int add = y;
        while(z != 0){
            if((z & 1) == 1){
                //ans + add < x
                if(ans < x - add){
                    return false;
                }
                ans += add;
            }

            //add + add < x
            if(z > 1 && add < x - add){
                return false;
            }
            add += add;
            z >>= 1;
        }
        return true;
    }
}

//官方解法：类二分查找（倍增）
class Solution1 {
    public int divide(int dividend, int divisor) {
        if(dividend == Integer.MIN_VALUE){
            if(divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }
        if(divisor == Integer.MIN_VALUE){
            if(dividend == Integer.MIN_VALUE){
                return 1;
            }
            return 0;
        }

        boolean negative = dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0;
        if(dividend > 0){
            dividend = -dividend;
        }
        if(divisor > 0){
            divisor = -divisor;
        }

        List<Integer> contributes = new ArrayList<>(32);
        int contribute = divisor;
        int max = 31;
        for(int i = 0; i < 32; i++){
            contributes.add(contribute);
            //contribute + contribute < dividend
            if(contribute < dividend - contribute){
                max = i;
                break;
            }
            contribute += contribute;
        }

        int ans = 0;
        for(int i = max; i >= 0; i--){
            if(contributes.get(i) >= dividend){
                ans += 1 << i;
                dividend -= contributes.get(i);
            }
        }
        return negative ? -ans : ans;
    }
}